Home | | Latest | About | Random
# Polynomial nonhomogeneous terms in a linear recurrence.
Suppose we have some sequence $(a_{n})$ over reals or complex such that it satisfies some $k$-th order linear recurrence $$
a_{n+k}+c_{1}a_{n+k-1}+\cdots+c_{k}a_{n}=p(n)
$$
where $p(n)$ is some polynomial over $\mathbb{C}$.
There are many ways to solve this, but there is once nice way by "splitting the polynomial", and making a substitution $a_{n}=b_{n}+q(n)$ for some suitable polynomial $q(n)$ such that $b_{n}$ satisfies a homogeneous linear recurrence.
Let us see how
Say one like to solve $a_{n+2}=a_{n+1}+2a_{n}+3n-2$. Suppose we have some $a_{n}=b_{n}+\lambda n+\mu$, then we must have $$
b_{n+2}+\lambda(n+2)+\mu=b_{n+1}+\lambda(n+1)+\mu+2b_{n}+2\lambda n+2\mu+3n-2
$$
If this is a homogeneous linear recurrence in $b_{n}$, then the other terms must sum to zero for all $n$, namely $$
\lambda(n+2)+\mu=\lambda(n+1)+\mu+2\lambda n+2\mu+3n-2
$$which gives a system of equation $$
\begin{align}
\lambda & =\lambda+2\lambda+3 \\
2\lambda+\mu & =\lambda+\mu+2\mu-2
\end{align}
$$
giving $\lambda=-\frac{3}{2}$ and $\mu=\frac{1}{4}$. Hence with $a_{n}=b_{n}-\frac{3}{2}n+\frac{1}{4}$ we have a homogeneous recurrence $b_{n+2}=b_{n+1}+2b_{n}$.
Oh, why do I call this "splitting the polynomial"? Let us look at this simpler example: $a_{n+1}=2a_{n}+3$. Then imagine we split the nonhomogeneous term $3=6-3$, then we have $a_{n+1}+3=2a_{n}+6=2(a_{n}+3)$, which we see the substitution $b_{n}=a_{n}+3$ gives a homogeneous linear recurrence. The observation that this can be done with powers of $n$ lead to this more generic method.
===
Is this always possible? **Generically**, yes. When $p(n)$ is of degree $m$, then we would in principle need a polynomial $q(n)$ also of degree $m$. For $a_{n+k}+c_{1}a_{n+k-1}+\cdots+c_{k}a_{n}=p(n)$, if $a_{n}=b_{n}+q(n)$, then we need $q(n+k)+c_{1}q(n+k-1)+\cdots+c_{k}q(n)=p(n)$. If both sides are degree $m$ polynomials, then we can solve the coefficients in $q$. **However**, there are situations where a naive choice of $q(n)$ would not be sufficient. In which we would need to bump up the degree of $q(n)$.
For instance, if we have $a_{n+1}-a_{n}=n$, then setting up $a_{n}=b_{n}+\lambda n+\mu$ would be disastrous: We get $b_{n+1}+\lambda(n+1)+\mu-b_{n}-\lambda n-\mu=n$, which we require $$
\lambda n+\lambda+\mu-\lambda n-\mu=n
$$
which gives $0=1$ inconsistency. But by setting $a_{n}=b_{n}+n(\lambda n+\mu)$ would avoid this problem. The reason being constants are already solutions to the homogeneous recurrence $a_{n+1}-a_{n}=0$. In this case $$
b_{n+1}+(n+1)(\lambda(n+1)+\mu)-b_{n}-n(\lambda n+\mu)=n
$$
So we need $$
(n+1)(\lambda(n+1)+\mu)-n(\lambda n+\mu)=n
$$
giving $2\lambda=1,\lambda+\mu=0$, so $a_{n}=b_{n}+n\left( \frac{1}{2}n-\frac{1}{2} \right)$ where $b_{n}$ satisfies the linear recurrence $b_{n+1}=b_{n}$, which gives constant solutions. Incidentally, this gives the triangular numbers and in general the Faulhaber's formulas.